package algorithm.hash;

import java.util.*;

class Solution {
    public static void main(String[] args) {
//        System.out.println((byte)127);
//        System.out.println((byte)128);
//        System.out.println((byte)129);
//        int[] nums = new int[]{3,7,5,2};
//        Arrays.sort(nums);
//        System.out.println(Arrays.toString(nums));
//        List<Integer> list = new ArrayList<>(Arrays.asList(1,23,22));
//        System.out.println(list);// [1, 23, 22]
//        List<String> list2 = new ArrayList<>(Arrays.asList("ss1","ss2","ss2"));
//        System.out.println(list2);//[ss1, ss2, ss2]

        String s= "%20";
        System.out.println("%20" + s);


    }

    public String dynamicPassword(String password, int target) {
        String sub1 = password.substring(0, target);
        String sub2 = password.substring( target);
        System.out.println(sub2 + sub1);
        return sub2 + sub1;
    }




    public String pathEncryption(String path) {
        char[] arr = path.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '.'){
                arr[i] = ' ';
            }
        }
        return new String(arr);
    }


    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();

        for (int i=0; i<arr.length; i=i+2*k){
            //这样，在最后一次移动后，区间元素可能不到2k, 要确定一下区间的终端。
            //对于每次从i开始 的 2k/k/<k s区间
            int start = i;
            //int end = Math.min( i + 2*k -1, arr.length-1) ;
            //反转的元素个数：判断尾数够不够k个来取决end指针的位置
            // < k个（剩余字符全部反转）
            // >k个 反转到start + k -1，
            int end = Math.min(start + k -1, arr.length-1) ;

            while (start< end) {
                char c = arr[start];
                arr[start] = arr[end];
                arr[end] = c;
                ++start;
                --end;
            }
        }
        return new String(arr);
    }



    public void reverseString(char[] s) {
        // hel  leh 双指针左右
        //原地修改输入数组
        int l = 0, r = s.length-1;
        while (l<r){
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            ++l;
            --r;
        }
    }




public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> res = new ArrayList<>();
    //先排序，便于去重
    Arrays.sort(nums);
    int len = nums.length;
    for (int i = 0; i < len -3; i++) {
        if (nums[i]>=0 && nums[i]>target){
            break;//后面的一定不成立了。 不能判断j, 因为j在中间
        }
        //对于已经重复了的元素，跳过此次的i，因为情况被判断过了
        if (i>0 && nums[i]== nums[i-1]) continue;

        for (int j = i+1; j < len-2; j++) {
            //对于已经重复了的元素，跳过此次的i，因为情况被判断过了
            if (j>i+1 && nums[j]== nums[j-1]) continue;

            //固定2个，移动2个。（这2个和固定，一方移动，另一方一定也移动：双指针）
            int left = j +1, right = len-1;//对于每对i、j: 它两的初始值。

            while (left < right){
                //target int会溢出
                long sum = (long) nums[i] + nums[j] +nums[left] + nums[right];
                if (sum >target){
                    right--;
                }else if (sum <target){
                    left++;
                }else {
                    res.add(Arrays.asList(nums[i],nums[j], nums[left], nums[right]));
                    //过掉 结果集中已经判断过 的元素。
                    //对于判断过、加入结果集的的此left，后面的是重复的元素，
                    while (left <right && nums[left]==nums[left+1])   ++left;
                    while (left <right && nums[right]==nums[right-1])   --right;
                    ++left;//判断下一个不同的元素。
                    --right;
                }
            }
        }

    }
    return res;
}


    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);//先排序，便于去重
        int len = nums.length;
        //3个数字，的最最左边
        for (int i = 0; i < len -2; i++) {
            //如果第一个数>0，sum一定>0 。。。往后都大于0
            if (nums[i] >0) return res;
            if (i>0 && nums[i] == nums[i-1]) continue; //跳过此次的i，因为元素已经重复了，情况被判断过了
            //对于每个i：L、R 从此开始
            int left = i+1, right = len -1;
            // 肯定不能重合、是实实在在的2个数字
            while (left< right){
                // 初始：第一次L、R不去重复。
                //对于此次的sum
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0){
                    right--;
                }else if (sum < 0){
                    left++;
                }else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //只有Sum=0，有结果了。才能去重。（否则就漏掉-1、-1、2类型的了）
                    //left去重 ，结果集已经判断过了相同的就不需要判断了，判断下一个left。
                    //使用while，因为可能 连续重复的元素有很多。
                    while ( left< right && nums[left] == nums[left+1])  left++;
                    while (left< right && nums[right] == nums[right-1])  right--; //right去重 ，是倒着顺序的
                    //sum =0 ,记得移动位置呀，判断下个条件
                    //为了保障Sum=0的结果集，只要L往前移动，变大。R一定要变小。L=  (Sum-num[i]) -R
                    //  不减 那就要二层循环分别判断了。
                    left++; right--;
                }
            }

        }
        return res;
    }



//    public List<List<Integer>> threeSum(int[] nums) {
//        List<List<Integer>> res = new ArrayList<>();
//        Arrays.sort(nums);//先排序，便于去重
//        int len = nums.length;
//        //3个数字，的最最左边
//        for (int i = 0; i < len -2; i++) {
//            //如果第一个数>0，sum一定>0 。。。往后都大于0
//            if (nums[i] >0) return res;
//            if (i>0 && nums[i] == nums[i-1]) continue; //跳过此次的i，因为元素已经重复了，情况被判断过了
//            //对于每个i：L、R 从此开始
//            int left = i+1, right = len -1;
//            // 肯定不能重合、是实实在在的2个数字
//            while (left< right){
//                // 初始：第一次L、R不去重复。
//                //对于此次的sum
//                int sum = nums[i] + nums[left] + nums[right];
//                if (sum > 0){
//                    right--;
//                }else if (sum < 0){
//                    left++;
//                }else {
//                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
//                    //sum =0 ,记得移动位置呀，判断下个条件
//                    //为了保障Sum=0的结果集，只要L往前移动，变大。R一定要变小。L=  (Sum-num[i]) -R
//                    // 结果集中：只要left++ ，right一定要同时--，才能使和为0。 不减 那就要二层循环分别判断了。
//                    left++; right--;
//                }
//               //每次去重。去重后while就可以判断 left< right 了。
//                if (nums[left] == nums[left-1])  left++; //left去重 ，此时不需要判断了，判断下一个left
//                if (right<len-1 && nums[right] == nums[right+1])  right--; //right去重 ，是倒着顺序的
//
//            }
//
//        }
//        return res;
//    }

    //哈希（相当于key是下标、value是次数）：小写英文字母就用26的数组(小写字母从a开始)。
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] hashArry = new int[26];
        //magazine 里面的字符个数 >= ransomNote
        for (int i = 0; i < magazine.length(); i++){
            char c = magazine.charAt(i);//字符
            hashArry[c-'a'] ++; //此字符出现的次数
        }

        for (int i = 0; i < ransomNote.length(); i++) {
            hashArry[ransomNote.charAt(i) - 'a'] --;
            // 看已有字符次数 能否满足需要 .
            // 只要>=0是ok的，但<0就不够了
            if(hashArry[ransomNote.charAt(i) - 'a'] <0) return false;
        }
        return true;
    }

    //对于 A、B，二重循环遍历存入哈希映射中（Key表示 A[i]+B[j]的值，value表示值 出现的次数。）
    //——变量count，用来统计 a+b+c+d = 0 出现的次数。
    //对于 C、D，也遍历。如果 0-(c+d)的值 在map中出现，就用count把map中key值对应的value也就是出现次数统计出来。
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> mapValueCount = new HashMap<>();
        for(int i =0; i < nums1.length; i++){
            for (int j = 0; j < nums2.length; j++) {
                //原有次数（0或其他）+1
                mapValueCount.put(nums1[i] + nums2[j],
                        mapValueCount.getOrDefault(nums1[i] + nums2[j],0) +1);
            }

        }
        int resCount = 0;
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                int cdNeed = 0- (nums3[i] + nums4[j]);
                if (mapValueCount.containsKey(cdNeed)){
                    resCount+=mapValueCount.get(cdNeed);
                }
            }
        }
        return resCount;
    }

    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        //创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，
        // (先判断是否包含、而不是先加入，以防止与自己匹配。)
        // 不存在：将 x 插入到哈希表中。
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            //key是元素（判断是否包含的）、value是下标(返回的)
            if (map.containsKey(target - nums[i])){
                res[0] = i;
                res[1] = map.get(target - nums[i]);
                return res;
            }
            map.put(nums[i], i);
        }
        return res;
    }


    //    public static void main(String[] args) {
//        boolean happy = isHappy(19);
//        System.out.println(happy);
//    }

    public static boolean isHappy(int n) {
        Set<Integer> sumSet = new HashSet<>(); //主要为了存平方和，判断是否已经包含了。
        while (n!=1 && !sumSet.contains(n)){
            sumSet.add(n);//add后一定包含呀，不能在最后一行。
            n = getSquareSum(n);//int newNum
        }
        //两种都情况都可以出来了，要判断
        return n == 1; //n==1?true:false
    }
    public static int getSquareSum(int n){
        int res = 0;
        //n = 255,  5方 + 5方 + 2方。
        while (n!=0){
            int num = n % 10; //取模（最后一位）
            res += num * num;
            n = n/10;     //更新去掉最后一位
        }
        return res;
    }




    public boolean isAnagram(String s, String t) {
        int[] table = new int[26];
        //记录字符串s里字符出现的次数。
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i) - 'a'] +=1;
        }
        //然后遍历t，减去对应字符的频次
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i) - 'a']--;
        }
        //=0,ok，
        // 不为零0，一定是谁多了字符或者谁少了字符。
        for (int count : table) {
            if (count != 0) return false;
        }
        return true;
    }
}